<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>53. 最大子数组和</title>
  </head>
  <body>
    <script>
      //     给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

      // 子数组 是数组中的一个连续部分。

      //

      // 示例 1：

      // 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
      // 输出：6
      // 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
      // 示例 2：

      // 输入：nums = [1]
      // 输出：1
      // 示例 3：

      // 输入：nums = [5,4,-1,7,8]
      // 输出：23

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/maximum-subarray
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * @param {number[]} nums
       * @return {number}
       */
      var maxSubArray = function (nums) {
        if (nums.length === 1) {
          return nums[0]
        }
        let maxArr = []
        let isAdd = true
        for (let i = 0; i < nums.length; i++) {
          if (isAdd && nums[i] < 0) {
            continue
          }
          if (isAdd && nums[i] >= 0) {
            maxArr.push(nums[i])
            isAdd = false
            continue
          }
          if (!isAdd && nums[i] < 0 && nums[i] + maxArr[maxArr.length - 1] <= 0) {
            isAdd = true
            continue
          }
          if (!isAdd && nums[i] < 0 && nums[i] + maxArr[maxArr.length - 1] > 0) {
            maxArr.push(maxArr[maxArr.length - 1])
            maxArr[maxArr.length - 1] += nums[i]
            continue
          }
          if (!isAdd && nums[i] >= 0) {
            maxArr[maxArr.length - 1] += nums[i]
            continue
          }
        }
        if (maxArr.length > 0) {
          return Math.max(...maxArr)
        } else {
          return Math.max(...nums)
        }
      }
      console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    </script>
  </body>
</html>
